package algorithm.sort.child;

import algorithm.sort.basic.Sort;

/**
 * 项目名称: god
 * 包 名 称: algorithm.sort.child
 * 类 名 称: CountSort2
 * 类 描 述: TODO
 * 创建时间: 2020/6/27 2:03 下午
 * 创 建 人: Justice
 * 计数排序
 */
public class CountSort2 extends Sort<Integer> {
    @Override
    protected void sort() {
        // 找出最值
        int max = array[0];
        int min = array[0];
        for (Integer integer : array) {
            if (integer < min) {
                min = integer;
            }
        }
        for (Integer integer : array) {
            if (integer > max) {
                max = integer;
            }
        }
        // 开辟内存空间，存储次数
        int[] counts = new int[max - min + 1];
        // 统计每个整数出现的次数
        for (Integer integer : array) {
            counts[integer - min]++;
        }
        // 累加次数
        for (int i = 1; i < counts.length; i++) {
            counts[i] += counts[i - 1];
        }
        // 从后往前遍历元素，将它放到有序数组中的合适位置
        int[] newArray = new int[array.length];
        for (int i = array.length - 1; i >= 0; i--) {
            newArray[--counts[array[i] - min]] = array[i];
        }
        // 将有序数组赋值到array
        for (int i = 0; i < newArray.length; i++) {
            array[i] = newArray[i];
        }
    }
}
